//0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
//
//
// 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
//
//
//
// 示例 1：
//
//
//输入: n = 5, m = 3
//输出: 3
//
//
// 示例 2：
//
//
//输入: n = 10, m = 17
//输出: 2
//
//
//
//
// 限制：
//
//
// 1 <= n <= 10^5
// 1 <= m <= 10^6
//
//
// Related Topics 递归 数学 👍 795 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
//? 超时做法
function lastRemaining(n: number, m: number): number {

    let arr = []
    let start = 0
    let last = 0
    let count = 0
    for (let i = 0; i < n; i ++) {
        arr[i] = i
    }
    while (arr.length > 1) {
        //? 记录个数
        let count = 0
        for (let i = start; count < m; i ++) {
            //? 到达最末尾 弄到首
            if (i === arr.length) {
                i = 0
            }
            count++
            last = i
        }
        arr.splice(last,1)
        start = last
    }
    return arr[0]
};
//leetcode submit region end(Prohibit modification and deletion)
//? 递归
function lastRemaining2(n: number, m: number): number {
    function travese(n, m) {
        //? 若只有 1 个人的时候，这个人就是活着的人
        if (n == 1) return 0;

        //? 每次循环右移
        return (travese(n - 1, m) + m) % n;
    }

    return travese(n, m);
};
//? 迭代
function lastRemaining3(n: number, m: number): number {
    //? 若只有 1 个人的时候，这个人就是活着的人
    let pos = 0;
    //? 需要 2 个人以上的时候，求出活着的人
    for (let i = 2; i <= n; i++) {
        //? 每次循环右移 找到该被杀的位置
        pos = (pos + m) % i;
    }

    return pos;
};
console.log(lastRemaining3(10, 17));
